Fork me on GitHub

算法--排序

字数统计: 4k字   |   阅读时长≈ 17分

排序

  • 直接插入排序
  • 希尔排序
  • 冒泡排序
  • 快速排序
  • 选择排序
  • 堆排序
  • 归并排序
  • 计数排序
  • 桶排序
  • 基数排序

  1. 直接插入排序：选取无序区的一个元素找到在有序区的插入位置，插入有序区（排扑克牌的过程）

    • 平均时间复杂度：O(n^2)
    • 空间复杂度：O(1)
    • 稳定性：稳定

    avatar

    avatar

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    /**
     * 插入排序
     * @param arr
     */
    public void insertSort(int[] arr) {
        //初始第一个元素为有序区，第二个数开始作为无序区，逐渐缩小无序区，扩大有序区
        for (int i = 1; i < arr.length; i++) {
            int val = arr[i];//每轮取无序区第一个数作为待插入元素
            int j=i-1;//有序区最后
            //寻找插入位置索引，在有序区最后从后往前检索
            while (j>=0&&val<arr[j]){
                arr[j+1]=arr[j];
                j--;
            }
            //找到插入位置
            if (j != i - 1) {
                arr[j + 1] = val;
            }
        }
    }

  1. 希尔排序（缩小增量法）：（直接插入排序优化）先选定一个整数gap（步长），把待排序序列中所有元素（n个）分成gap个组，所有距离为gap的元素分在同一组内，并对每一组内的元素进行直接插入排序。然后将gap逐渐减小，重复上述分组和排序的工作，当到达gap=1时，排序前的数据已将近正序，所有元素在统一组内排好序，gap=0时结束。（效率高于直接插入排序，但不稳定）

    • 平均时间复杂度：O(nlogn)
    • 空间复杂度：O(1)
    • 稳定性：不稳定

    取gap=n/2为例：

    avatar

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public void shellSort(int[] arr) {
        for (int gap = arr.length >> 1; gap > 0; gap = gap >> 1) {//缩小步长
            //直接插入排序（原直接插入排序相当于步长为1的情况，所以对原插入排序有1的地方改为gap即可）
            for (int i = gap; i < arr.length; i++) {
                int val = arr[i];
                int j=i-gap;
                while (j>=0&&val<arr[j]){
                    arr[j+gap]=arr[j];
                    j-=gap;
                }
                if (j != i - gap) {
                    arr[j + gap] = val;
                }
            }
        }
    }

  1. 冒泡排序：每一轮从头开始，从前往后两两元素进行比较，前一个比后一个大就交换，直到将最大的元素交换到末尾位置，每轮减少一个元素

    • 平均时间复杂度：O(n^2)
    • 空间复杂度：O(1)
    • 稳定性：稳定

    avatar

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    /**
     * 冒泡排序
     * @param arr
     */
    public void bubbleSort(int[] arr){
        boolean isSwap=false;//看一轮中是否交换过元素，如果没交换过，则说明序列有序，不用进行后面的轮
        for (int i = 0; i < arr.length-1; i++) {//最后一轮只剩一个元素，不用进行
            for (int j = 0; j < arr.length - i-1; j++) {//每轮最后一个元素不用往后比较
                if (arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    isSwap=true;
                }
            }
            if (!isSwap){
                break;
            }
            isSwap=false;
        }
    }

    /**
     * 交换
     * @param arr
     * @param i
     * @param j
     */
    private void swap(int[] arr, int i, int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

  1. 快速排序：基于分治思想排序，将某元素作为基准值，把比基准值小的调整到基准值左边，递归切分基准值左右两部分，按同样规则进行调整

    • 平均时间复杂度:O(nlogn)
    • 空间复杂度:O(logn)
    • 稳定性:不稳定

    调整具体思路是：

    • 选定一个基准值（为了方便选区间最左边那个）
    • 确定两个指针 l 和 r，分别从区间两边向中间走,r指针找比基准值小的，l指针找比基准值大的，指针移动时，让r指针先走
    • 两指针停下后交换对应位置的值
    • 继续向下走，重复以上步骤，直到两指针重合时，最后将基准值与重合位置值进行交换。

    为什么要让r指针先走？

    最后是要把相遇位置处的数和基准位置处的数进行交换，要保证交换到基准值位置的数比基准值小，如果让l指针（找大的）先走，l指针先停下，两指针相遇时会找到一个比基准值大的数和基准值交换，所以得让r指针（找小的）先走

    [6,1,2,7,9,3,4,5,10,8]调整过程：

    avatar

    完整快速排序过程：

    avatar

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    /**
     * 快速排序
     * @param arr
     */
    public void quickSort(int[] arr){
        split(arr,0,arr.length-1);
    }

    /**
     * 切分
     * @param arr
     * @param left
     * @param right
     */
    private void split(int[] arr,int left,int right){
        if (left>=right){
            return;
        }
        int p=partition(arr,left,right);
        split(arr,left,p-1);//切分基准值左半部分
        split(arr,p+1,right);//切分基准值右半部分
    }

    /**
     * 小于基准值的调整到基准值左边
     * @param arr
     * 区间
     * @param left
     * @param right
     * @return 交换后的基准值索引
     */
    private int partition(int[] arr, int left, int right) {
        int i=left;
        int j=right;
        int pv=arr[left];//每次为区间最左边的那个
        while (i<j){
            while (i<j&&arr[j]>pv){//找比基准值小的
                j--;
            }
            while (i<j&&arr[i]<=pv){//找比基准值大的
                i++;
            }
            swap(arr,i,j);
        }
        swap(arr,left,i);
        return i;
    }

    /**
     * 交换
     * @param arr
     * @param i
     * @param j
     */
    private void swap(int[] arr, int i, int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

  1. 选择排序：每轮在区间中选择一个最小的排在该轮区间最前面

    • 平均时间复杂度：O(n^2)
    • 空间复杂度：O(1)
    • 稳定性：不稳定

    avatar

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    /**
     * 选择排序
     * @param arr
     */
    public void selectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int min = findMin(arr, i);
            swap(arr,i,min);
        }
    }

    /**
     * @param arr
     * @param left
     * @return 数组区间从[left~最后一个元素]最小值索引
     */
    private int findMin(int[] arr,int left){
        int minVal=arr[left];
        int minIndex=left;
        for (int i = left+1; i <arr.length; i++) {
            if (minVal>arr[i]){
                minVal=arr[i];
                minIndex=i;
            }
        }
        return minIndex;
    }

    /**
     * 交换
     * @param arr
     * @param i
     * @param min
     */
    private void swap(int[] arr, int i, int min) {
        int temp=arr[i];
        arr[i]=arr[min];
        arr[min]=temp;
    }
  1. 堆排序：每轮将待排的无序序列调整成堆结构，将堆顶最值交换到最后，每轮减少一个元素

  • 基本思路：

    • 升序采用大顶堆（由于大根堆每轮最大的会被交换到最后，形成升序序列），降序采用小顶堆
    • 首先将待排序的数组调整成一个堆（大根堆/小根堆），此时，整个数组的最大（小）值就是堆顶
    • 将堆顶元素与末尾的元素交换，此时，末尾的元素为最大（小）值，剩余待排序序列个数为n-1个
    • 将剩余的n-1个数再调整成堆（大根堆/小根堆），由于交换后只有堆顶元素不符合堆结构，所以对堆顶元素执行下潜即可，再将堆顶元素与n-1位置的元素交换，如此反复执行，便能得到有序序列

  • 平均时间复杂度：O(nlogn)

  • 空间复杂度：O(1)

  • 稳定性：不稳定

    堆：一种完全二叉树

    • 大顶堆：每个父结点的值都大于其左右孩子的值
    • 小顶堆：每个父结点的值都小于其左右孩子的值

    avatar

    数组表示：

    avatar

    数组中某个元素的父结点及其左右孩子索引:

    • 父节点索引为i
      • 左孩子索引：2*i+1
      • 右孩子索引：2*i+2（左孩子索引+1）
    • 左孩子索引为j
      • 父节点索引：(j-1)/2
    • 最后一个非叶子结点索引：数组长度/2-1
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    /**
     * 堆排序
     * @param arr
     */
    public void heapSort(int[] arr){
        heapify(arr);//建堆
        int size=arr.length;
        while (size>1){//交换堆顶元素和末尾元素
            swap(arr,0,size-1);
            size--;
            down(arr,0,size);//重新调整堆结构
        }
    }

    /**
     * 建堆
     * @param arr
     */
    private void heapify(int[] arr) {
        //从后往前第一个非叶子结点开始下潜（弗洛伊德建堆O(logn)）（另一种威廉姆斯建堆，边添加结点边调整堆结构O(nlogn)）
        for (int i = arr.length / 2 - 1; i >=0 ; i--) {
            down(arr,i,arr.length);
        }
    }

    /**
     * 下潜
     * @param arr
     * @param i 开始结点索引
     * @param n 结束索引
     */
    private void down(int[] arr, int i,int n) {
        int max=i;
        int left=i*2+1;//左孩子索引
        int right=left+1;//右孩子索引
        //父节点和左右孩子中选一个最大的（大顶堆）（若选最小的为小顶堆）
        if (left<n&&arr[max]<arr[left]){
            max=left;
        }
        if (right<n&&arr[max]<arr[right]){
            max=right;
        }
        if (max!=i){
            swap(arr,i,max);
            down(arr,max,n);//继续下潜
        }
    }

    /**
     * 交换
     * @param arr
     * @param i
     * @param j
     */
    private void swap(int[] arr, int i, int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

  1. 归并排序：基于分治思想的排序算法

    • 思想
      • 分：切分原始数组（向下）
      • 治：两子序列合并成有序序列
      • 合：有序序列继续和其他序列合并（向上）
    • 平均时间复杂度：O(nlogn)
    • 空间复杂度：O(n)
    • 稳定性：稳定

    avatar

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    /**
     * 归并排序
     * @param arr
     */
    public void mergeSort(int[] arr){
        if (arr.length==0){
            return;
        }
        int[] temp=new int[arr.length];
        split(arr,0,arr.length-1,temp);
    }

    /**
     * 切分
     * @param arr
     * @param left 左边界
     * @param right 右边界
     * @param temp 临时数组，合并时用
     */
    private void split(int[] arr, int left, int right,int[] temp) {
        if (left==right){
            return;
        }
        int mid=left+right>>>1;
        split(arr,left,mid,temp);//左半部分切分
        split(arr,mid+1,right,temp);//右半部分切分
        merge(arr,left,mid,mid+1,right,temp);//合并成有序序列(结果在临时数组中)
        System.arraycopy(temp,left,arr,left,right-left+1);//合并结果存回原数组，继续合并
    }

    /**
     * 合并（数组两区间合并成有序序列存于临时数组中）
     * @param arr
     * @param left
     * @param leftEnd
     * @param right
     * @param rightEnd
     * @param temp
     */
    private void merge(int[] arr, int left, int leftEnd, int right, int rightEnd,int[] temp) {
        int i=left;
        int j=right;
        int k=left;
        while (i<=leftEnd&&j<=rightEnd){
            if (arr[i]<arr[j]){
                temp[k]=arr[i];
                i++;
            }else {
                temp[k]=arr[j];
                j++;
            }
            k++;
        }
        if (j>rightEnd){
            System.arraycopy(arr,i,temp,k,leftEnd-i+1);
        }
        if (i>leftEnd){
            System.arraycopy(arr,j,temp,k,rightEnd-j+1);
        }
    }

  1. 计数排序：使用一个count[]数组来统计原数组每个元素出现的个数，count数组值作为元素个数值，索引作为元素值(索引和元素值之间的关系为相对值，不一定与元素值相等，建立一种映射关系)，再根据个数把对应元素写回原数组

    • 平均时间复杂度：O(n+k) （k为count[]大小，n元素个数）
    • 空间复杂度：O(k)
    • 稳定性：可稳定或不稳定

    avatar

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    /**
     * 只针对元素大于0计数排序（可通过此理解和改写成通用版本）
     * @param arr
     */
    public void countSort(int[] arr){
        //求最大
        int max=arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (max<arr[i]){
                max=arr[i];
            }
        }
        //计数数组
        int[] count=new int[max+1];
        //统计元素个数
        for (int i : arr) {
            count[i]++;
        }
        //写回原数组
        int j=0;
        for (int i = 0; i < count.length; i++) {
            while (count[i]>0){
                arr[j++]=i;
                count[i]--;
            }
        }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    /**
     * 计数排序
     * @param arr
     */
    public void countSort(int[] arr){
        //求最大最小值
        int max=arr[0];
        int min=arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (max<arr[i]){
                max=arr[i];
            }
            if (min>arr[i]){
                min=arr[i];
            }
        }
        //计数数组
        int[] count=new int[max-min+1];
        //统计元素个数
        for (int i : arr) {
            count[i-min]++;
        }
        //写回原数组
        int j=0;
        for (int i = 0; i < count.length; i++) {
            while (count[i]>0){
                arr[j++]=i+min;
                count[i]--;
            }
        }
    }
  1. 桶排序：将数组元素分散到多个桶，保证索引小的桶装小的元素，索引大的桶装大的元素，然后进行桶内排序后，接着按顺序取桶，最后把桶内元素写回原数组

  • 平均时间复杂度：O(n+k) (k为桶个数，n为元素个数)

  • 空间复杂度：O(n+k)

  • 稳定性：稳定

    avatar

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    /**
     * 桶排序（此版本结合计数排序方便理解和改进）
     * @param arr
     */
    public void bucketSort(int[] arr){
        //求最大值和最小值，max-min得数据范围
        int max=arr[0];
        int min=arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]>max){
                max=arr[i];
            }
            if (arr[i]<min){
                min=arr[i];
            }
        }
        //初始化桶（max-min+1为数据范围内的每个数分配一个桶）
        ArrayList[] buckets=new ArrayList[max-min+1];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i]=new ArrayList();
        }
        //将数组元素分散到桶（元素值-min可以分配到对应桶且桶内元素只有一个，元素和桶具有映射关系
        // ->和计数排序类似，这样保证了小桶装小元素，大桶装大元素，因为只有一个元素，所以可以不用进行桶内排序
        // 所以按顺序取桶，写元素即可，但空间浪费大）
        for (int i : arr) {
            buckets[i-min].add(i);
        }

        int k=0;

        for (ArrayList bucket : buckets) {
            //桶内排序
            //bucket.sort(Comparator.comparingInt(o -> (Integer) o));

            //将桶内元素放回原数组
            for (Object o : bucket) {
                arr[k]= (int) o;
                k++;
            }
        }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    /**
     * 桶排序（改进版）
     * @param arr
     * @param range 控制桶的数量和桶内元素个数
     */
    public void bucketSort(int[] arr,int range){
        //求最大值和最小值，max-min得数据范围
        int max=arr[0];
        int min=arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]>max){
                max=arr[i];
            }
            if (arr[i]<min){
                min=arr[i];
            }
        }
        //初始化桶（max-min+1为数据范围内的每个数分配一个桶） （除range减少桶数量）
        ArrayList[] buckets=new ArrayList[(max-min)/range+1];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i]=new ArrayList();
        }
        //将数组元素分散到桶（元素值-min可以分配到对应桶且桶内元素只有一个，元素和桶具有映射关系
        // ->和计数排序类似，这样保证了小桶装小元素，大桶装大元素，且只有一个元素
        // 所以这样按顺序取桶元素，可以不用进行桶内排序，但空间浪费大）
        for (int i : arr) {
            //（除range约束多个元素为一组，减少桶数量，桶内有多个元素了，所以得进行桶内排序）
            buckets[(i-min)/range].add(i); 
        }

        int k=0;

        for (ArrayList bucket : buckets) {
            //桶内排序
            bucket.sort(Comparator.comparingInt(o -> (Integer) o));

            //将桶内元素放回原数组
            for (Object o : bucket) {
                arr[k]= (int) o;
                k++;
            }
        }
    }
  1. 基数排序：以下采用LDS，即从个位开始，从右向左对每一位进行排序。初始化[0 ~ 9]个桶，刚开始按个位大小将每个元素分散到对应的桶（个位为0的装入0号桶，以此类推），个位分散完之后，再按桶顺序取出元素写回原数组，再进行下一轮百位的排序，以此类推。
    - 平均时间复杂度：O(k*n) (k位数，n元素个数)
    - 空间复杂度：O(m) (m桶个数)
    - 稳定性：稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * 基数排序（LDS 从右向左）
 *
 * @param arr
 */
public void radixSort(int[] arr) {
    if (arr.length == 0) {
        return;
    }
    //初始化[0~9]个桶
    ArrayList[] buckets = new ArrayList[10];
    for (int i = 0; i < buckets.length; i++) {
        buckets[i] = new ArrayList();
    }

    //求最大值和最小值位数，位数大的为处理次数
    int max = arr[0];
    int min = arr[0];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    int maxBit = (max + "").length();
    int minBit = (min + "").length() - 1;
    int n = Integer.max(maxBit, minBit);

    //个位->百位->千位···的顺序进行
    int m = 1;
    for (int i = 0; i < n; i++) {
        //取数组元素分散到对应桶
        for (int ele : arr) {
            ele = ele - min;//负数也可以转换为>0的数，保证有桶可装
            int j = ele / m % 10;
            buckets[j].add(ele);
        }

        //按桶顺序将桶内元素取出放回原数组，进行下一轮分散到桶
        int k = 0;
        for (ArrayList bucket : buckets) {
            for (Object ele : bucket) {
                arr[k++] = (int) ele + min;//还原元素原始值
            }
            bucket.clear();//清空桶
        }

        m *= 10;
    }

java中Arrays.sort()根据数据量不同和特性采用不同排序算法。

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

主要涉及技术：
Java开发

联系QQ:1445911979

如有错误，请帮忙指正，谢谢大家~~